#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		string ss;
		cin >> ss;
		
		if(ss=="FIFO")
		{
			queue <int> s;
			while(n--)
			{
				string a;
				cin >> a;
				if(a=="IN")
				{
					int x;
					cin >> x;
					s.push(x);
				}
				else if(a=="OUT")
				{
					if(!s.empty())
					{
						cout << s.front() << endl;
						s.pop();
					}
					
					else
					cout << "None" << endl;
				}
			}
		}
		else if(ss=="FILO")
		{
			stack <int> s;
			while(n--)
			{
				string a;
				if(a=="IN")
				{
					int x;
					cin >> x;
					s.push(x);
				}
				else if(a=="OUT")
				{
					if(!s.empty())
					{
						cout << s.top() << endl;
						s.pop();
					}
					
					else
					cout << "None" << endl;
				}
			}
		}
	}
	return 0;
}
